package leetcode;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/*
    给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
    请你将两个数相加，并以相同形式返回一个表示和的链表。
    你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

    示例 1：
    输入：l1 = [2,4,3]
         l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807

    示例 2：
    输入：l1 = [0], l2 = [0]
    输出：[0]

    示例 3：
    输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

    提示：
    每个链表中的节点数在范围 [1, 100] 内
    0 <= Node.val <= 9
    题目数据保证列表表示的数字不含前导零
 */
public class AddTwoNumbers {
    private ListNode l1;
    private ListNode l2;

    @Before
    public void dataInit() {
        // l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
        // 初始化 l1: 2 -> 4 -> 3 (代表数字 342)
        l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
//        l1 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
        // 初始化 l2: 5 -> 6 -> 4 (代表数字 465)
        l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
//        l2 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))));
    }

    @Test
    public void method_0() {
        System.out.println(l1.toString());
        System.out.println(l2.toString());
    }

    @Test //
    public void method_1() {
        int l1_l = l1.length();
        int l2_l = l2.length();
        double l1_num = 0;
        double l2_num = 0;
        for (int i = 0; i < l1_l; i++) {
            l1_num += l1.val * Math.pow(10, i);
            if (l1.next == null){
                break;
            }
            l1 = l1.next;
        }
        System.out.println(l1_num);

        for (int i = 0; i < l2_l; i++) {
           l2_num += l2.val * Math.pow(10, i);
           if (l2.next == null){
               break;
           }
           l2 = l2.next;
        }
        System.out.println(l2_num);
        String s = String.valueOf((int) (l1_num + l2_num));
        String[] result = new String[s.length()];
        for (int i = 0; i < s.length(); i++) {
            result[i] = s.charAt(i) + "";
        }
        System.out.println(Arrays.toString( result));
//        while (l1.next != null){
//            System.out.println(l1.val);
//            l1 = l1.next;
//            if (l1.next == null){
//                System.out.println(l1.val);
//                return;
//            }
//        }
//        System.out.println(l1.length());
    }

    @Test // 对method_1的优化
    public void method_2() {
        // ✅ 优化1：使用标准逐位相加算法（避免精度丢失）
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        // ✅ 优化2：直接遍历链表，无需长度计算
        ListNode p = l1;
        ListNode q = l2;

        while (p != null || q != null || carry != 0) {
            int a = (p != null) ? p.val : 0;
            int b = (q != null) ? q.val : 0;

            int sum = a + b + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;

            // 移动指针
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }

        // ✅ 优化3：直接返回结果链表（无需转换数字）
        ListNode result = dummy.next;

        // 验证输出（示例：7 0 8）
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();
    }

    // ✅ 优化4：使用标准链表相加算法  最优解决方案
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int a = (l1 != null) ? l1.val : 0;
            int b = (l2 != null) ? l2.val : 0;

            int sum = a + b + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next;
    }

    @Test
    public void method_3() {
        long s = System.currentTimeMillis();
        // 初始化链表
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

        // 执行加法
        ListNode result = addTwoNumbers(l1, l2);
        System.out.println("结果：" + result.toString());

        // 验证输出: 7 -> 0 -> 8
        assert result.val == 7;
        assert result.next.val == 0;
        assert result.next.next.val == 8;
        assert result.next.next.next == null;
        System.out.println("执行时间：" + (System.currentTimeMillis() - s));
    }
}
